package NC102_在二叉树中找到两个节点的最近公共祖先;

import java.util.*;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
}

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        Map<Integer, Integer> parent = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        parent.put(root.val, Integer.MIN_VALUE);    // 根节点没有父节点，给一个默认值
        queue.add(root);
        // 直到两个结点都找到为止
        while (!parent.containsKey(o1) || !parent.containsKey(o2)){
            TreeNode node = queue.poll();
            if (node.left != null){
                parent.put(node.left.val, node.val);
                queue.add(node.left);
            }
            if (node.right != null){
                parent.put(node.right.val, node.val);
                queue.add(node.right);
            }
        }
        Set<Integer> ancestors = new HashSet<>();
        // 记录下o1和他的祖先节点，从o1结点开始一直到根节点
        while (parent.containsKey(o1)){
            ancestors.add(o1);
            o1 = parent.get(o1);
        }
        // 查看o1和他的祖先结点是否包含o2结点，如果不包含再看是否包含o2的父节点
        while (!ancestors.contains(o2)){
            o2 = parent.get(o2);
        }
        return o2;
    }
}